package io.github.hadyang.leetcode.offer;

import io.github.hadyang.leetcode.ListNode;
import java.util.HashSet;
import java.util.Set;

/** @author haoyang.shi */
public class FindFirstCommonNode {

  /**
   * 空间 O(n)
   *
   * @param pHead1
   * @param pHead2
   * @return
   */
  public ListNode FindFirstCommonNode_1(ListNode pHead1, ListNode pHead2) {
    Set<ListNode> node1s = new HashSet<>();

    while (pHead1 != null) {
      node1s.add(pHead1);
      pHead1 = pHead1.next;
    }

    while (pHead2 != null) {
      if (node1s.contains(pHead2)) {
        return pHead2;
      }

      pHead2 = pHead2.next;
    }

    return null;
  }

  /**
   * 空间 O(1)
   *
   * @param pHead1
   * @param pHead2
   * @return
   */
  public ListNode FindFirstCommonNode_2(ListNode pHead1, ListNode pHead2) {
    int len1 = 0, len2 = 0;
    ListNode cursor1 = pHead1, cursor2 = pHead2;
    while (cursor1 != null) {
      cursor1 = cursor1.next;
      len1++;
    }

    while (cursor2 != null) {
      cursor2 = cursor2.next;
      len2++;
    }

    cursor1 = pHead1;
    cursor2 = pHead2;
    if (len1 > len2) {
      int i = len1;
      while (i != len2) {
        cursor1 = cursor1.next;
        i--;
      }
    } else if (len1 < len2) {
      int i = len2;
      while (i != len1) {
        cursor2 = cursor2.next;
        i--;
      }
    }

    while (cursor1 != null && cursor2 != null) {
      if (cursor1 == cursor2) {
        return cursor1;
      }

      cursor1 = cursor1.next;
      cursor2 = cursor2.next;
    }

    return null;
  }
}
